SherbyNet - /page/wikibook/entry.mu

Micron Document

<!DOCTYPE html>

<title>Pointer machine</title>

</head>

Pointer machine

</h1>

</header>

<div id="mw-content-text" class="mw-body-content mw-content-ltr" lang="en" dir="ltr"><div class="mw-content-ltr mw-parser-output" lang="en" dir="ltr">In <a href="Theoretical_computer_science" title="Theoretical computer science">theoretical computer science</a>, a pointer machine is an atomistic <a href="Abstract_machine" title="Abstract machine">abstract computational machine</a> whose storage structure is a <a href="Graph_(discrete_mathematics)" title="Graph (discrete mathematics)">graph</a>. A pointer algorithm could also be an <a href="Algorithm" title="Algorithm">algorithm</a> restricted to the pointer machine model.<a href="#cite_note-1">[1]</a>

Some particular types of pointer machines are called a linking automaton, a KU-machine, an SMM, an atomistic LISP machine, a tree-pointer machine, etc.<a href="#cite_note-ben-amram-2">[2]</a>

Pointer machines do not have arithmetic instructions. Computation proceeds only by reading input symbols, modifying and doing various tests on its storage structure—the pattern of nodes and pointers, and outputting symbols based on the tests. In this sense, the model is similar to the <a href="Turing_machine" title="Turing machine">Turing machine</a>.

<div class="mw-heading mw-heading2"><h2 id="Types_of_"pointer_machines"">Types of "pointer machines"</h2></div>

Both Gurevich and Ben-Amram list a number of very similar "atomistic" models of "abstract machines";<a href="#cite_note-Gurevich-3">[3]</a><a href="#cite_note-ben-amram-2">[2]</a> Ben-Amram believes that the "atomistic models" must be distinguished from "high-level" models. The following atomistic models will be presented below:

<ul><li>Schönhage's storage modification machines (SMM),<a href="#cite_note-Schonhage-4">[4]</a></li>

<li>Kolmogorov–Uspenskii machines (KUM or KU-Machines).<a href="#cite_note-5">[5]</a></li></ul>

Ben-Amram also presents the following varieties, not further discussed in this article:

<ul><li>Atomistic pure-LISP machine (APLM)</li>

<li>Atomistic full-LISP machine (AFLM),</li>

<li>General atomistic pointer machines,</li>

<li>Jone's I language (two types).</li></ul>

<div class="mw-heading mw-heading2"><h2 id="Schönhage's_storage_modification_machine_(SMM)_model">Schönhage's storage modification machine (SMM) model</h2></div>

The following presentation follows van Emde Boas.<a href="#cite_note-vEB-6">[6]</a>

The machine consists of a fixed alphabet of input symbols, a fixed program, and a mutable <a href="Directed_graph" title="Directed graph">directed graph</a> with its arrows labelled by alphabet symbols. The graph is the machine's storage. Each node of the graph has exactly one outgoing arrow labelled with each symbol, although some of these may loop back into the original node. One fixed node of the graph is identified as the start or "active" node.

Each word of symbols in the alphabet can then be translated to a pathway through the machine; for example, 10011 would translate to taking edge 1 from the start node, then edge 0 from the resulting node, then edge 0, then edge 1, then edge 1. Thus a word identifies a node, the final node of the path, but this identification will change as the graph changes during the computation.

The machine can receive instructions which change the layout of the graph. The basic instructions are:

(1) new w instruction, which creates a new node at the end of the path w, with all its edges directed to the next-to-last node in w.

(2) set w to v instruction which (re)directs an edge to a different node. Here w and v represent words. The instruction results in changing the destination of the last edge in the path w.

(3) If v = w then instruction z : Conditional instruction that compares two paths represented by words w and v to see if they end at the same node; if so jump to instruction z else continue. This instruction serves the same purpose as the if command in any imperative programming language.

(4) read and write instructions for input/output, accessing a read-only input tape and a write-only output tape, both containing symbols of the alphabet.

<a href="Donald_Knuth" title="Donald Knuth">Knuth</a> noted that the SMM model coincides with a type of "linking automaton" briefly explained in volume one of <a href="The_Art_of_Computer_Programming" title="The Art of Computer Programming">The Art of Computer Programming</a>.<a href="#cite_note-Schonhage-4">[4]</a>

<div class="mw-heading mw-heading2"><h2 id="Kolmogorov–Uspenskii_machine_(KU-machine)_model">Kolmogorov–Uspenskii machine (KU-machine) model</h2></div>

KUM differs from SMM in allowing only invertible pointers: for every pointer from a node x to a node y, an inverse pointer from y to x must be present, labeled by the same symbol. In other words, the storage graph is undirected. Since outgoing pointers must be labeled by distinct symbols of the alphabet, both KUM and SMM graphs have O(1) outdegree. However, KUM pointers' invertibility restricts the in-degree to O(1), as well. This addresses some concerns for physical (as opposite to purely informational) realism.

There are other, minor differences between the models, such as the form of the program - a state table instead of a list of instructions.

<div class="mw-heading mw-heading2"><h2 id="Considerations_regarding_the_pointer-machine_model">Considerations regarding the pointer-machine model</h2></div>

Use of the model in complexity theory:

van Emde Boas (1990) expresses concern that this form of abstract model is:

<dl><dd>"an interesting theoretical model, but ... its attractiveness as a fundamental model for complexity theory is questionable. Its time measure is based on uniform time in a context where this measure is known to underestimate the true time complexity. The same observation holds for the space measure for the machine" (van Emde Boas (1990) p. 35)</dd></dl>

Gurevich also expresses concern:

<dl><dd>"Pragmatically speaking, the Schönhage model provides a good measure of time complexity at the current state of the art (though I would prefer something along the lines of the random access computers of Angluin and Valiant)".<a href="#cite_note-7">[7]</a></dd></dl>

Schönhage demonstrates the real-time equivalences of two types of <a href="Random-access_machine" title="Random-access machine">random-access machine</a> with the SMM.<a href="#cite_note-Schonhage-4">[4]</a>

Algorithms in the SMM model: Schönhage demonstrates that the SMM can perform integer multiplication in linear time.<a href="#cite_note-Schonhage-4">[4]</a>

Potential uses for the model: Gurevich wonders whether or not a parallel KU machine "resembles somewhat the human brain"<a href="#cite_note-8">[8]</a>

Parallel computing: All the models mentioned above are sequential. A parallel (atomistic) pointer machine model has been proposed by Cook and Dymond;<a href="#cite_note-9">[9]</a> a high-level (non-atomistic) parallel pointer machine model has also been used<a href="#cite_note-10">[10]</a>

<a href="Register_machine" title="Register machine">Register machine</a>—generic register-based <a href="Abstract_machine" title="Abstract machine">abstract machine</a> computational model

<ul><li><a href="Counter_machine" title="Counter machine">Counter machine</a>—most primitive machine, base models' instruction-sets are used throughout the class of register machines</li>

<li><a href="Random-access_machine" title="Random-access machine">Random-access machine</a>—RAM: counter machine with added indirect addressing capability</li>

<li><a href="Random-access_stored-program_machine" title="Random-access stored-program machine">Random-access stored-program machine</a>—RASP: counter-based or RAM-based machine with a "program of instructions" to be found in the registers themselves in the manner of a <a href="Universal_Turing_machine" title="Universal Turing machine">Universal Turing machine</a> i.e. the <a href="Von_Neumann_architecture" title="Von Neumann architecture">von Neumann architecture</a>.</li></ul>

<a href="Turing_machine" title="Turing machine">Turing machine</a>—generic tape-based <a href="Abstract_machine" title="Abstract machine">abstract machine</a> computational model

<ul><li><a href="Post%E2%80%93Turing_machine" title="Post–Turing machine">Post–Turing machine</a>—minimalist one-tape, two-direction, 1 symbol { blank, mark } Turing-like machine but with default sequential instruction execution in a manner similar to the basic 3-instruction counter machines.</li></ul>

<div class="mw-heading mw-heading2"><h2 id="Further_reading">Further reading</h2></div>

Most references and a bibliography are to be found at the article <a href="Register_machine" title="Register machine">Register machine</a>. The following are particular to this article:

<ul><li>Amir Ben-Amram (1995), <a rel="nofollow" class="external text" href="http://www2.mta.ac.il/~amirben/downloadable/pm.ps.gz">What is a "Pointer machine"?</a>, SIGACT News (ACM Special Interest Group on Automata and Computability Theory)", volume 26, 1995. Wherein Ben-Amram describes the types and subtypes: (type 1a) Abstract Machines: Atomistic models including Kolmogorov-Uspenskii Machines (KUM), Schönhage's Storage Modification Machines (SMM), Knuth's "Linking Automaton", APLM and AFLM (Atomistic Pure-LISP Machine) and (Atomistic Full-LISP machine), General atomistic Pointer Machines, Jone's I Language; (type 1b) Abstract Machines: High-level models, (type 2) Pointer algorithms.</li>

<li><a href="Yuri_Gurevich" title="Yuri Gurevich">Yuri Gurevich</a> (2000), Sequential Abstract State Machines Capture Sequential Algorithms, ACM Transactions on Computational Logic, vol. 1, no. 1, (July 2000), pages 77–111. In a single sentence Gurevich compares the Schönhage [1980] "storage modification machines" to Knuth's "pointer machines." For more, similar models such as "random access machines" Gurevich references:

<ul><li><a href="John_E._Savage" title="John E. Savage">John E. Savage</a> (1998), <a rel="nofollow" class="external text" href="https://web.archive.org/web/20161105053330/http://cs.brown.edu/~jes/book/">Models of Computation: Exploring the Power of Computing</a>. Addison Wesley Longman.</li></ul></li>

<li><a href="Yuri_Gurevich" title="Yuri Gurevich">Yuri Gurevich</a> (1988), <a rel="nofollow" class="external text" href="https://web.eecs.umich.edu/~gurevich/Opera/78.pdf">On Kolmogorov Machines and Related Issues</a>, the column on "Logic in Computer Science", Bulletin of European Association for Theoretical Computer Science, Number 35, June 1988, 71-82. Introduced the unified description of Schönhage and Kolmogorov-Uspenskii machines used here.</li>

<li><a href="Arnold_Sch%C3%B6nhage" title="Arnold Schönhage">Arnold Schönhage</a> (1980), Storage Modification Machines, Society for Industrial and Applied Mathematics, SIAM J. Comput. Vol. 9, No. 3, August 1980. Wherein Schönhage shows the equivalence of his SMM with the "successor RAM" (Random Access Machine), etc. He refers to an earlier paper where he introduces the SMM:

<ul><li><a href="Arnold_Sch%C3%B6nhage" title="Arnold Schönhage">Arnold Schönhage</a> (1970), Universelle Turing Speicherung, Automatentheorie und Formale Sprachen, Dörr, Hotz, eds. Bibliogr. Institut, Mannheim, 1970, pp. 69–383.</li></ul></li>

<li><a href="Peter_van_Emde_Boas" title="Peter van Emde Boas">Peter van Emde Boas</a>, Machine Models and Simulations pp. 3–66, appearing in:</li></ul>

<dl><dd><dl><dd><a href="Jan_van_Leeuwen" title="Jan van Leeuwen">Jan van Leeuwen</a>, ed. Handbook of Theoretical Computer Science. Volume A: Algorithms and Complexity, The MIT PRESS/Elsevier, 1990. <style data-mw-deduplicate="TemplateStyles:r1238218222">

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-444-88071-2</bdi> (volume A).</dd></dl></dd>

<dd>van Emde Boas' treatment of SMMs appears on pp. 32-35. This treatment clarifies Schönhage 1980 -- it closely follows but expands slightly the Schönhage treatment. Both references may be needed for effective understanding.</dd></dl>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

<li id="cite_note-1"><a href="#cite_ref-1">^</a> <cite id="CITEREFCloteauxRanjan2006" class="citation web cs1">Cloteaux, Brian; Ranjan, Desh (2006). <a rel="nofollow" class="external text" href="https://www.researchgate.net/publication/221467378">"Some Separation Results Between Classes of Pointer Algorithms"</a>.</cite>

</li>

<li id="cite_note-ben-amram-2">^ <a href="#cite_ref-ben-amram_2-0">a</a> <a href="#cite_ref-ben-amram_2-1">b</a> Amir Ben-Amram (1995). What is a "Pointer machine"?, SIGACT News (ACM Special Interest Group on Automata and Computability Theory), volume 26, 1995.

</li>

<li id="cite_note-Gurevich-3"><a href="#cite_ref-Gurevich_3-0">^</a> <a href="Yuri_Gurevich" title="Yuri Gurevich">Yuri Gurevich</a> (2000), Sequential Abstract State Machines Capture Sequential Algorithms, ACM Transactions on Computational Logic, vol. 1, no. 1, (July 2000), pages 77–111.

</li>

<li id="cite_note-Schonhage-4">^ <a href="#cite_ref-Schonhage_4-0">a</a> <a href="#cite_ref-Schonhage_4-1">b</a> <a href="#cite_ref-Schonhage_4-2">c</a> <a href="#cite_ref-Schonhage_4-3">d</a> <a href="Arnold_Sch%C3%B6nhage" title="Arnold Schönhage">Arnold Schönhage</a> (1980), Storage Modification Machines, SIAM Journal on Computing Vol. 9, No. 3, August 1980.

</li>

<li id="cite_note-5"><a href="#cite_ref-5">^</a> <a href="Andrey_Kolmogorov" title="Andrey Kolmogorov">Andrey Kolmogorov</a> and <a href="Vladimir_Andreyevich_Uspensky" class="mw-redirect" title="Vladimir Andreyevich Uspensky">V. Uspenskii</a>, On the definition of an algorithm, Uspekhi Mat. Nauk 13 (1958), 3-28. English translation in American Mathematical Society Translations, Series II, Volume 29 (1963), pp. 217–245.

</li>

<li id="cite_note-vEB-6"><a href="#cite_ref-vEB_6-0">^</a> <a href="Peter_van_Emde_Boas" title="Peter van Emde Boas">Peter van Emde Boas</a>, Machine Models and Simulations pp. 3–66 in: <a href="Jan_van_Leeuwen" title="Jan van Leeuwen">Jan van Leeuwen</a>, ed. Handbook of Theoretical Computer Science. Volume A: Algorithms and Complexity, The MIT PRESS/Elsevier, 1990. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-444-88071-2</bdi> (volume A).

</li>

<li id="cite_note-7"><a href="#cite_ref-7">^</a> Gurevich (1988) p. 6 with reference to Angluin D. and Valiant L. G., "Fast Probabilistic Algorithms for Hamiltonian Circuits and Matchings", Journal of Computer and System Sciences 18 (1979) 155-193.

</li>

<li id="cite_note-8"><a href="#cite_ref-8">^</a> <a href="Yuri_Gurevich" title="Yuri Gurevich">Yuri Gurevich</a> (1988), <a rel="nofollow" class="external text" href="http://research.microsoft.com/~gurevich/Opera/78.pdf">On Kolmogorov Machines and Related Issues</a>, the column on "Logic in Computer Science", Bulletin of European Association for Theoretical Computer Science, Number 35, June 1988, 71-82.

</li>

<li id="cite_note-9"><a href="#cite_ref-9">^</a> <cite id="CITEREFCookDymond1993" class="citation journal cs1">Cook, Stephen A.; Dymond, Patrick W. (March 1993). "Parallel pointer machines". Computational Complexity. 3: 19–30. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2FBF01200405">10.1007/BF01200405</a>.</cite>

</li>

<li id="cite_note-10"><a href="#cite_ref-10">^</a> <cite id="CITEREFGoodrichKosaraju1996" class="citation journal cs1">Goodrich, M. T.; Kosaraju, S. R. (1996). "Sorting on a parallel pointer machine with applications to set expression evaluation". Journal of the ACM. 43 (2): 331–361. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F226643.226670">10.1145/226643.226670</a>.</cite>

</li>

</ol></div></div></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-04-22" href="https://en.wikipedia.org/wiki/?title=Pointer_machine&oldid=1286928397">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>